⟸ pàgina anterior ⟸

Exercici 5 (Tasca 2).

(regular languages, reverse)

El revessat d’un llenguatge regular és regular

1. Construïu de forma explícita el DFA mínim per al llenguatge L^R, on

   1. L=\{w\in\{a,b\}^*\mid \forall w_1,w_2\ (w=w_1aw_2\Rightarrow |w_1|_b\in 2\mathbb N )\}.
   2. L=\{w\in\{a,b\}^*\mid \forall w_1,w_2\ (w=w_1aw_2\Rightarrow |w_1|_b\in 2\mathbb N +1)\}.
   3. L=\{w\in\{a,b\}^*\mid \forall w_1,w_2\ (w=w_1aw_2\Rightarrow |w_1|\in 2\mathbb N )\}.

   Construïu el DFA mínim que reconeix L. A partir d’aquí, construïu un NFA A que reconegui el llenguatge L^R. Fent servir la construcció del conjunt de parts, determinitzeu A i finalment minimitzeu el DFA obtingut.

2. Donat un DFA A com a entrada, quin és el cost de construir un DFA per a L(A)^R?

3. Revessar la direcció de les transicions i intercanviar estats inicials i finals en un DFA A produeix un NFA B per a L(A)^R. Si l’NFA obtingut és de fet un DFA i A és mínim, és B mínim?

4. Un NFA és d’acceptació única si per tot mot existeix una única execució acceptadora. Demostreu que, per a un NFA A d’acceptació única, l’NFA A^R és d’acceptació única.